package Week.Double004;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

import static java.util.Arrays.*;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/16 17:48
 */
public class problem03 {
    double maximumAverage=0;
    public double maximumAverageSubtree(TreeNode root) {
        if(root==null){
            return maximumAverage;
        }
        getTempResult(root);
        return maximumAverage;
    }

    private TempResult getTempResult(TreeNode root){
        TempResult tempResult=new TempResult();
        if(root.left==null&&root.right==null){
            tempResult.average=root.val;
            tempResult.nodeNum=1;
            tempResult.sum=root.val;
            maximumAverage=Math.max(maximumAverage, tempResult.average);
        }else if(root.left==null){
            TempResult rightTempResult=getTempResult(root.right);
            tempResult.nodeNum=rightTempResult.nodeNum+1;
            tempResult.sum=rightTempResult.sum+root.val;
            tempResult.average=tempResult.sum/tempResult.nodeNum;
            maximumAverage=Math.max(maximumAverage, tempResult.average);
        }else if(root.right==null){
            TempResult leftTempResult=getTempResult(root.left);
            tempResult.nodeNum=leftTempResult.nodeNum+1;
            tempResult.sum=leftTempResult.sum+root.val;
            tempResult.average=tempResult.sum/tempResult.nodeNum;
            maximumAverage=Math.max(maximumAverage, tempResult.average);
        }else {
            TempResult leftTempResult=getTempResult(root.left);
            TempResult rightTempResult=getTempResult(root.right);
            tempResult.nodeNum=leftTempResult.nodeNum+rightTempResult.nodeNum+1;
            tempResult.sum=leftTempResult.sum+rightTempResult.sum+root.val;
            tempResult.average=tempResult.sum/tempResult.nodeNum;
            maximumAverage=Math.max(maximumAverage, tempResult.average);
        }
        return tempResult;
    }
    public class TempResult{
        int nodeNum;
        int average;
        int sum;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


    public int maxNumberOfApples(int[] arr) {
        sort(arr);
        int num=0;
        for(int i=0;i<arr.length;i++){
            num+=arr[i];
            if(num>5000){
                return i;
            }
        }
        return arr.length;
    }

    public int smallestCommonElement(int[][] mat) {
        if(mat==null||mat.length==0||mat[0].length==0){
            return -1;
        }
        if(mat.length==1){
            return mat[0][0];
        }

        List<Integer> minList= new ArrayList<>();
        for(int i=0;i<mat[0].length;i++){
            minList.add(mat[0][i]);
        }

        for(int i=1;i<mat.length;i++){

            int[] tempArray=mat[i];
            for(int j=0;j<minList.size();j++){
                int num=minList.get(j);
                if(!check(num,tempArray)){
                    minList.remove(j);
                }
            }

            if(minList.size()==0){
                return -1;
            }

        }
        return minList.get(0);

    }

    public int minKnightMoves(int x, int y) {

        int newX=x+300;
        int newY=y+300;

        return getStep(0,newX,newY);


    }

    private Integer getStep(int curStep,int x,int y){
        if(x>600||x<0||y>600||y<0){
            return Integer.MAX_VALUE;
        }
        if(x==300||y==300){
            return curStep;
        }
        return Math.min(getStep(curStep+1,x+1,y+2),
                Math.min(getStep(curStep+1,x+1,y-2),
                        Math.min(getStep(curStep+1,x-1,y+2),
                                getStep(curStep+1,x-1,y-2))));
    }

    private boolean check(Integer num,int[] tempArray){
        for(int i=0;i<tempArray.length;i++){
            if(tempArray[i]==num){
                return true;
            }
            if(tempArray[i]>num){
                return false;
            }
        }
        return false;
    }

}
